/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Kevin Lim
 */

#include "base/intmath.hh"
#include "cpu/edge/pred/tournament.hh"
#include "cpu/base.hh"

template<class Impl>
TournamentBP<Impl>::TournamentBP(unsigned _localPredictorSize,
                           unsigned _localHistoryTableSize,
                           unsigned _localHistoryBits,
                           unsigned _globalPredictorSize,
                           unsigned _globalHistoryBits,
                           unsigned _choiceHistoryBits,
                           unsigned _choicePredictorSize,
                           unsigned _choiceCtrBits,
                           unsigned _blockShiftAmt)
    : localPredictorSize(_localPredictorSize),
      localHistoryTableSize(_localHistoryTableSize),
      localHistoryBits(_localHistoryBits),
      globalPredictorSize(_globalPredictorSize),
      globalHistoryBits(_globalHistoryBits),
      choiceHistoryBits(_choiceHistoryBits),
      choicePredictorSize(_choicePredictorSize),
      choiceCtrBits(_choiceCtrBits),
      blockShiftAmt(_blockShiftAmt)
{
    if (!isPowerOf2(localPredictorSize)) {
        fatal("Invalid local predictor size!\n");
    }

    /** Setup the array of counters for the local predictor */
    localCtrs.resize(localPredictorSize);

    for (int i = 0; i < localPredictorSize; ++i) {
        localCtrs[i].exitID = 0;
	localCtrs[i].hysteresis = 0;
    }

    localPredictorMask = floorPow2(localPredictorSize) - 1;

    if (!isPowerOf2(localHistoryTableSize)) {
        fatal("Invalid local history table size!\n");
    }

    /** Setup the history table for the local table */
    localHistoryTable.resize(localHistoryTableSize);

    for (int i = 0; i < localHistoryTableSize; ++i)
        localHistoryTable[i] = 0;

    /** Setup the history table for the local futrue file */
    localFutureFile.resize(Impl::MaxInFlightBlockNum);

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        localFutureFile[i].index = 0;
	localFutureFile[i].history = 0;
    }
    /** Setup the local history mask */
    localHistoryMask = (ULL(0x1) << localHistoryBits) - 1;

    if (!isPowerOf2(globalPredictorSize)) {
        fatal("Invalid global predictor size!\n");
    }

    /** Setup the array of counters for the global predictor */
    globalCtrs.resize(globalPredictorSize);

    for (int i = 0; i < globalPredictorSize; ++i) {
        globalCtrs[i].hysteresis = 0;
	globalCtrs[i].exitID = 0;
    }
    /** Clear the global history */
    for (int i = 0; i < Impl::MaxThreads ;++i )
	globalHistory[i] = 0;

    globalPredictorMask = floorPow2(globalPredictorSize) - 1;
    /** Setup the global history mask */
    globalHistoryMask = (ULL(0x1) << globalHistoryBits) - 1;

    globalHistoryFile.resize(Impl::MaxInFlightBlockNum);
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
	globalHistoryFile[i] = 0;

    choiceHistoryFile.resize(Impl::MaxInFlightBlockNum);
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
	choiceHistoryFile[i] = 0;
	
    if (!isPowerOf2(choicePredictorSize)) {
        fatal("Invalid choice predictor size!\n");
    }
    /** Clear the choice history */
    for (int i = 0; i < Impl::MaxThreads; ++i)
        choiceHistory[i] = 0;

    choicePredictorMask = floorPow2(choicePredictorSize) - 1;

    /** Setup the choice history mask */
    choiceHistoryMask = (ULL(0x1) << choiceHistoryBits) - 1;
    
    /** Setup the array of counters for the choice predictor */
    choiceCtrs.resize(choicePredictorSize);

    for (int i = 0; i < choicePredictorSize; ++i)
        choiceCtrs[i].setBits(choiceCtrBits);

    threshold = (ULL(0x1) << (choiceCtrBits - 1)) - 1;
    threshold = threshold / 2;
}

template<class Impl>
TournamentBP<Impl>::~TournamentBP()
{
    DPRINTF(EdgePredUnit,"Tournament destructed!\n");
}

template<class Impl>
void
TournamentBP<Impl>::reset()
{
    for (int i = 0; i < localPredictorSize; ++i) {
        localCtrs[i].exitID = 0;
	 localCtrs[i].hysteresis = 0;
    }
	
    for (int i = 0; i < globalPredictorSize; ++i) {
        globalCtrs[i].hysteresis = 0;
	 globalCtrs[i].exitID = 0;
    }
	
    //Clear the global history
    for (int i = 0; i < Impl::MaxThreads ;++i )
	globalHistory[i] = 0;
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
	globalHistoryFile[i] = 0;
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
	choiceHistoryFile[i] = 0;
	
    //Clear the choice history
    for (int i = 0; i < Impl::MaxThreads; ++i)
        choiceHistory[i] = 0;
    
    for (int i = 0; i < choicePredictorSize; ++i)
        choiceCtrs[i].setBits(choiceCtrBits);    
}

template<class Impl>
inline
uint32_t
TournamentBP<Impl>::calcLocHistIdx(Addr &block_addr,int addr_space_ID)
{
    // Get low order bits after removing instruction offset.
    assert(addr_space_ID >= 0 && addr_space_ID <= 15);
    int reverse_as_id = ((addr_space_ID & 0x1) << 3)
                        | ((addr_space_ID & 0x2) << 1)
                        | ((addr_space_ID & 0x4) >> 1)
                        | ((addr_space_ID & 0x8) >> 3);
    return ((block_addr >> blockShiftAmt) ^ (reverse_as_id << (localHistoryBits -4))) 
		& (localHistoryTableSize - 1);
}

template<class Impl>
inline
uint32_t
TournamentBP<Impl>::calcLocPredIdx(Addr &block_addr,uint32_t history)
{
    uint32_t index = (history ^ (block_addr >> blockShiftAmt)) & localPredictorMask;
    return index;
}

template<class Impl>
inline
uint32_t
TournamentBP<Impl>::calcGloPredIdx(Addr &block_addr,uint32_t history)
{
    uint32_t index = (history ^ (block_addr >> blockShiftAmt)) & globalPredictorMask;
    return index;
}

template<class Impl>
inline
uint32_t
TournamentBP<Impl>::calcChoiPredIdx(Addr &block_addr,uint32_t history)
{
    uint32_t index = (history ^ (block_addr >> blockShiftAmt)) & choicePredictorMask;
    return index;
}

template<class Impl>
unsigned
TournamentBP<Impl>::lookupGetIndex(Addr &block_PC, ThreadID tid)
{
    unsigned choice_history = choiceHistory[tid] & choiceHistoryMask;
    unsigned choice_predictor_idx = calcChoiPredIdx(block_PC, choice_history);
    return choice_predictor_idx;
}

template<class Impl>
unsigned
TournamentBP<Impl>::updateGetIndex(BlockID blockID, Addr &block_PC, ThreadID tid)
{
    unsigned index = blockID &(Impl::MaxInFlightBlockNum -1);
    unsigned choice_predictor_hist = choiceHistoryFile[index];
    unsigned choice_predictor_idx = calcChoiPredIdx(block_PC, choice_predictor_hist);
    return choice_predictor_idx;
}

template<class Impl>
TheISA::ExitID
TournamentBP<Impl>::lookup(BlockID blockID, BlockID oldest_blockID, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    ExitID local_prediction;
    uint32_t local_history_idx;
    uint32_t local_history;
    uint32_t local_predictor_idx;

    uint32_t global_history;
    uint32_t global_predictor_idx;
    ExitID global_prediction;

    uint32_t choice_history;
    uint32_t choice_predictor_idx;
    bool choice_prediction;
    ExitID prediction;

    uint32_t global_history_new;
    uint32_t choice_history_new;
    LFFEntry lff_entry_new;

    //Get local history.
    local_history_idx = calcLocHistIdx(block_addr, addr_space_ID);
    local_history = localHistoryTable[local_history_idx];

    if (blockID != oldest_blockID && oldest_blockID != 0) {
        BlockID tmp_bid = blockID; // latest block

        do {
  	    LFFEntry lff_entry;
            tmp_bid = (tmp_bid - 1) & 0x7;
            lff_entry = localFutureFile[tmp_bid];
            if (lff_entry.index == local_history_idx)
            {
                local_history = lff_entry.history;
                break;
            }
        } while (tmp_bid != (oldest_blockID & 0x7));
    }

    //Lookup local predication
    local_predictor_idx = calcLocPredIdx(block_addr, local_history);
    local_prediction = localCtrs[local_predictor_idx].exitID;

    //Get global history
    global_history = globalHistory[tid] & globalHistoryMask;
    global_predictor_idx = calcGloPredIdx(block_addr,global_history);
    
    //Lookup in the global predictor to get its branch prediction
    global_prediction = globalCtrs[global_predictor_idx].exitID;

    //Get choice history
    choice_history = choiceHistory[tid] & choiceHistoryMask;
    choice_predictor_idx = calcChoiPredIdx(block_addr,choice_history);
    //Lookup in the choice predictor to see which one to use
    choice_prediction = choiceCtrs[choice_predictor_idx].read() > threshold;

    // Final prediction
    prediction= choice_prediction ? global_prediction : local_prediction;

    DPRINTF(EdgePredUnit,"BP: global prediction = %i, local_prediction = %i"
            " for %#x.\n",
            global_prediction,local_prediction,block_addr);

    // Speculative update
    uint32_t index = blockID & (Impl::MaxInFlightBlockNum - 1); 
    globalHistoryFile[index] = global_history;
    global_history_new = ((global_history << 2) | (prediction & 3)) &
                         globalHistoryMask ;
    globalHistory[tid] = global_history_new;

    choiceHistoryFile[index] = choice_history;
    choice_history_new = ((choice_history << 3) | (prediction & 7)) &
                         choiceHistoryMask ;
    choiceHistory[tid] = choice_history_new;

    lff_entry_new.index = local_history_idx;
    lff_entry_new.history = ((local_history << 2) | (prediction & 3)) &
                            localHistoryMask;
    localFutureFile[index] = lff_entry_new;
    return prediction;
}

template<class Impl>
void
TournamentBP<Impl>::update(BlockID blockID, Addr &block_addr, 
        int addr_space_id,ExitID actual_exitID,ThreadID tid)
{
    uint32_t local_history_idx;
    uint32_t local_predictor_hist;
    uint32_t local_predictor_hist_new;
    uint32_t global_predictor_hist;
    uint32_t choice_predictor_hist;
    uint32_t local_predictor_idx;
    uint32_t global_predictor_idx;
    uint32_t choice_predictor_idx;

    PredictionTableEntry local_predictor_entry, local_predictor_entry_new;
    PredictionTableEntry global_predictor_entry, global_predictor_entry_new;

    assert(actual_exitID >= 0 && actual_exitID <= 7);

    // Read L1 tables of exit predictor
    uint32_t index = blockID & (Impl::MaxInFlightBlockNum -1);
    local_history_idx = calcLocHistIdx(block_addr, addr_space_id);
    local_predictor_hist = localHistoryTable[local_history_idx];
    global_predictor_hist = globalHistoryFile[index];
    choice_predictor_hist = choiceHistoryFile[index];

    //Update L1 tables
    local_predictor_hist_new = ((local_predictor_hist << 2) |
                               (actual_exitID & 3)) & localHistoryMask;

    localHistoryTable[local_history_idx] = local_predictor_hist_new;
    
    // Read and update L2 tables
    local_predictor_idx = calcLocPredIdx(block_addr, local_predictor_hist);
    local_predictor_entry = localCtrs[local_predictor_idx];

    local_predictor_entry_new.exitID = local_predictor_entry.hysteresis ?
        local_predictor_entry.exitID : actual_exitID ;

    local_predictor_entry_new.hysteresis =
        (local_predictor_entry.exitID == actual_exitID);

    localCtrs[local_predictor_idx] = local_predictor_entry_new;
	
    global_predictor_idx = calcGloPredIdx(block_addr, global_predictor_hist);
    global_predictor_entry = globalCtrs[global_predictor_idx];
    global_predictor_entry_new.exitID = global_predictor_entry.hysteresis ?
        global_predictor_entry.exitID : actual_exitID ;
    global_predictor_entry_new.hysteresis =
        (global_predictor_entry.exitID == actual_exitID);
    globalCtrs[global_predictor_idx] = global_predictor_entry_new;

    DPRINTF(EdgePredUnit,"BPUpdate: exitID = %i ,global predictor = %i(%i), "
		"and local predictor = %i(%i).\n", actual_exitID,
		global_predictor_entry_new.exitID,global_predictor_entry.exitID,
		local_predictor_entry_new.exitID,local_predictor_entry.exitID);
    choice_predictor_idx = calcChoiPredIdx(block_addr, choice_predictor_hist);

    if (local_predictor_entry.exitID != global_predictor_entry.exitID) {
        if(local_predictor_entry.exitID == actual_exitID) {
            choiceCtrs[choice_predictor_idx].decrement();
	} else if(global_predictor_entry.exitID == actual_exitID) {
            choiceCtrs[choice_predictor_idx].increment();
        }
    }
}

template<class Impl>
void
TournamentBP<Impl>::squash(BlockID blockID, ExitID exitID, ThreadID tid)
{
    unsigned global_history;
    unsigned choice_history;
    unsigned index = blockID&(Impl::MaxInFlightBlockNum -1) ;

    LFFEntry oldLFFEntry, newLFFEntry;
    oldLFFEntry = localFutureFile[index];
    newLFFEntry.index = oldLFFEntry.index;
    newLFFEntry.history = ((oldLFFEntry.history & (~3)) | (exitID & 3))
                          & localHistoryMask;
    localFutureFile[index] = newLFFEntry;

    // Restore global history to state prior to this branch.
    global_history = globalHistoryFile[index];
    globalHistory[tid] = ((global_history << 2) | (exitID & 3)) & globalHistoryMask ;
    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = ((choice_history << 3) | (exitID & 7)) & choiceHistoryMask ;
    DPRINTF(EdgePredUnit,"Squashing BP to Block [bid:%i].\n",blockID);
    // Delete this BPHistory now that we're done with it.
}

template<class Impl>
void
TournamentBP<Impl>::squash(BlockID blockID,ThreadID tid)
{
    unsigned index = blockID&(Impl::MaxInFlightBlockNum -1);
    unsigned global_history;
    unsigned choice_history;
    global_history = globalHistoryFile[index];
    globalHistory[tid] = global_history;
    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = choice_history;
}

